HW#5 --- last modified March 02 2019 21:31:39..

Solution set.

Due date: Dec 6

Files to be submitted:
  Hw5.zip

Purpose: To learn about oracles and relativization techniques. To learn about one-way functions. To learn about self-reducibility and hashing techniques in complexity. To understand monotone circuit lower bound results.

Related Course Outcomes:

Problem 1 is related to course outcome (5) [Know conditions under which various of these hierarchies might collapse ].

Problem 2 and 3 are related to course outcome (7) [Exhibit a relativized separation (oracle result) of complexity classes for standard classes such as P and NP].

The programming assignment is related to course outcome (6) [Explain at least one circuit lower bound technique such as Razborov's techniques for monotone circuits].

Specification:

For the noncoding part of the assignment do the following problems and submit them in Hw5.tex:

1. Call a language simple if all the strings in it come from {w}^* where w∈{0,1}^*. Call a language finitely simple if it is the finite union of simple languages. Show that if a finitely simple language is NP-complete then P=NP.

2. Exhibit an oracle set A with respect to which UP is different from P, and hence, with respect to which there exist one way functions.

3. Exhibit an oracle A under which NP ∩ coNP has complete problems, yet NP^A≠P^A.

For the coding part of the assignment I want you to write a program called CrudeCircuitMaker.java . This program will be tested from the command line with a line like:

java CrudeCircuitMaker circuit.txt l p

Here l and p will be positive integer numbers like 3 or 5. circuit.txt will be a file containing a monotone circuit. The format for circuits will be the same as in HW3 except that as the circuit is monotone the file won't have any rows corresponding to not gates. Your program should then output a sequence of rows that correspond to the variables in each set of the crude circuit that would be constructed by the rules given on page 345-346 in the text. (The crude circuits in the proof of Razborov's lower bound for Clique_n,k.) If the number of variables is greater than 10 you may use a blackslash in your output to continue it to an additional line per every 10 variables. An example output line might be:

2 9 34 5 6 7 99 4 82 81\ 21 91 30

Notice a space is used to delimit variables. 34 in the above corresponds to the variable x₃₄.

Use a blank line to separate each set of the crude circuit in the output

Point Breakdown